This invention relates to key distribution schemes for transfer and authentication of encryption keys.
Diffie-Hellman key agreement provided the first practical solution to the key distribution problem, in cryptographic systems. The key agreement protocol allowed two parties never having met in advance or shared key material to establish a shared secret by exchanging messages over an open (unsecured) channel. The security rests on the intractability of the Diffie-Hellman problem and the related problem of computing discrete logarithms.
With the advent of the Internet and such like the requirement for large-scale distribution of public keys and public key certificates are becoming increasingly important. Public-key certificates are a vehicle by which public keys may be stored, distributed or forwarded over unsecured media without danger of undetectable manipulation. The objective is to make one parties"" public key available to others such that its authenticity and validity are verifiable.
A public-key certificate is a data structure consisting of a data part and a signature part. The data part contains cleartext data including as a minimum, public key and a string identifying the party to be associated therewith. The signature part consists of the digital signature of a certification authority (CA) over the data part, thereby binding the entities identity to the specified public key. The CA is a trusted third party whose signature on the certificate vouches for the authenticity of the public key bound to the subject entity.
Identity-based systems (ID-based system) resemble ordinary public-key systems, involving a private transformation and a public transformation, but parties do not have explicit public keys as before. Instead, the public key is effectively replaced by a party""s publicly available identity information (e.g. name or network address). Any publicly available information, which uniquely identifies the party and can be undeniably associated with the party, may serve as identity information.
An alternate approach to distributing public keys involves implicitly certified public keys. Here explicit user public keys exist, but they must be reconstructed rather than transported by public-key certificates as in certificate based systems. Thus implicitly certified public keys may be used as an alternative means for distributing public keys (e.g. Diffie-Hellman keys).
An example of an implicitly certified public key mechanism is known as Gunther""s implicitly-certified (ID-based) public key method. In this method:
1. A trusted server T selects an appropriate fixed public prime p and generator xcex1 of Zp*. T selects a random integer t, with 1xe2x89xa6txe2x89xa6pxe2x88x922 and gcd(t, pxe2x88x921)=1, as its private key, and publishes its public key u=xcex1t mod p, along with xcex1, p.
2. T assigns to each party A a unique name or identifying string IA and a random integer kA with gcd(kA, pxe2x88x921)=1. T then computes PA=xcex1kA mod p. PA is A""s KEY reconstruction public data, allowing other parties to compute (PA)a below.
3. Using a suitable hash function h, T solves the following equation for a:
H(IA)xe2x89xa1t.PA+kA a (mod pxe2x88x921)
4. T securely transmits to A the pair (r,s)=(PA, a), which is T""s ElGamal signature on IA. (a is A""s private key for Diffie-Hellman key-agreement)
5. Any other party can then reconstruct A""s Diffie-Hellman public key PAa entirely from publicly available information (xcex1, IA, u, PA, p) by computing:
PAaxe2x89xa1xcex1h(IA)uxe2x88x92PA mod p
Thus for discrete logarithm problems, signing a certificate needs one exponentiation operation, but reconstructing the ID-based implicitly-verifiable public key needs two exponentiations. It is known that exponentiation in the group Zp* and its analog scalar multiplication of a point in E(Fq) is computationally intensive. For example an RSA scheme is extremely slow compared to elliptic curve systems. However despite the resounding efficiency of EC systems over RSA type systems this is still a problem particularly for computing devices having limited computing power such as xe2x80x9csmart cardsxe2x80x9d, pagers and such like.
The present invention seeks to provide an efficient ID-based implicit certificate scheme, which provides improved computational speeds over existing schemes. For convenience, we describe the schemes over Zp, however these schemes are equally implementable in elliptic curve cryptosystems.
In accordance with this invention there is provided a method of generating an identity-based public key in a secure digital communication system, having at least one trusted entity CA and subscriber entities A, the method comprising the steps of:
(a) for each entity A, the CA selecting a unique identity IA distinguishing the entity A;
(b) generating a public key reconstruction public data xcex3A of entity A by mathematically combining a generator of the trusted party CA with a private value of the entity A, such that the pair (IA, xcex3A) serves as A""s implicit certificate;
(c) combining the implicit certificate information (IA, xcex3A) in accordance with a mathematical function F(xcex3A, IA) to derive an entity information f;
(d) generating a private key a of the entity A by signing the entity information f and
transmitting the private key a to the entity A, whereby the entity A""s public key may be reconstructed from the public information, the generator xcex3A and the identity IA relatively efficiently.
In accordance with a further embodiment of the invention there is provided a public key certificate comprising a plurality of public keys having different bit strengths and wherein one of the public keys is an implicitly certified public key.